/**
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
 *
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/word-break
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 思路：动态规划
 * 方法：动态规划
 * 状态：
 *
 *  子状态：前1，2，3，...,n个字符能否根据词典中的词被成功分词
 *
 *  F(i): 前i个字符能否根据词典中的词被成功分词
 * 状态递推：
 *
 *  F(i): true{j <i && F(j) && substr[j+1,i]能在词典中找到} OR false
 *
 *  在j小于i中，只要能找到一个F(j)为true，并且从j+1到i之间的字符能在词典
 *
 *  中找到，则F(i)为true
 *
 * 初始值：
 *
 *  对于初始值无法确定的，可以引入一个不代表实际意义的空状态，作为状态的起始
 *
 *  空状态的值需要保证状态递推可以正确且顺利的进行，到底取什么值可以通过简单
 *
 *  的例子进行验证
 *
 *  F(0) = true
 *
 * 返回结果：F(n）
 */
class WordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
     int len=s.length();
     boolean[] canBreak=new boolean[len+1];
     canBreak[0]=true;
     for(int i=1;i<=len;i++){
         for(int j=0;j<i;j++) {
             if(canBreak[j]&&(wordDict.contains(s.substring(j,i)))) {
                 canBreak[i]=true;
                 break;
             }
         }
     }   
     return canBreak[len];
    }
}